МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
/
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
МЕТОДИ АНАЛІЗУ ТА СИНТЕЗУ
КОМБІНАЦІЙНИХ СХЕМ.
КОМБІНАЦІЙНІ СХЕМИ З БАГАТЬМА ВИХОДАМИ (СУМІСНА МІНІМІЗАЦІЯ)
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи №3
з дисципліни «Обчислювальна техніка»
для студентів базового напрямку 6.0914
«Комп’ютеризовані системи, автоматика і управління»
Затверджено
на засіданні кафедри
«Автоматика і телемеханіка»
Протокол № 10 від 22.02.2001р.
Львів - 2001
Мета роботи: вивчення методів сумісної мінімізації систем логічних функцій; аналізу і синтезу комбінаційних логічних схем з багатьма виходами.
1. ОСНОВНІ ВІДОМОСТІ
Сумісна мінімізація систем логічних функцій потрібна при проектуванні комбінаційних схем з багатьма виходами. Саме такі схеми описуються системою логічних функцій, число яких дорівнює числу виходів схеми.
Задача сумісної мінімізації системи m логічних функцій від n змінних полягає у виявленні та раціональному використанні спільних логічних виразів. Якщо виконувати незалежну мінімізацію окремо кожної функції системи, то хоч кожна з цих функцій буде мінімальною, але в цілому система найчастіше виявляється немінімальною.
Відомо кілька способів сумісної мінімізації. Ці способи ділять на дві групи. До першої групи відносять методи, що використовують нормальні (дворівневі) канонічні форми функцій. До другої групи відносять методи, що використовують багаторівневі представлення функцій.
Найпоширеніший метод сумісної мінімізації першої групи грунтується на знаходженні простих імплікант, якими покривається кожна функція заданої системи. Цей метод нагадує метод Квайна і може бути описаний наступним алгоритмом:
Записати кожну функцію заданої системи в досконалій диз’юнктивній нормальній формі (ДДНФ) і сформувати повну множину А мінтермів, які відповідають одиничним значенням всіх функцій системи. Кожному мінтерму множини А приписати ознаку входження в ДДНФ тої чи іншої функції системи.
Здійснити мінімізацію допоміжної функції Z, ДДНФ якої містить всі мінтерми множини А. В процесі мінімізації, виконуючи склеювання мінтермів або імплікант, результату склеювання присвоїти ознаку, що складається з номерів функцій, спільних для мінтермів або імплікант, що склеюються. Якщо ознаки мінтермів або імплікант не містять однакових номерів, склеювання не здійснюється. Поглинання здійснюється тільки для кон’юнкцій з однаковими ознаками. Отримані внаслідок склеювання і поглинання кон’юнкції називають простими імплікантами системи функцій.
Для допоміжної функції Z побудувати імплікантну таблицю, подібну до матриці Квайна, але для кожного мінтерма виділити стільки стовпців, скільки різних номерів функцій містить ознака цього мінтерма. Покриття мінтермів імплікантами здійснюється за методом Квайна.
Таблиця 1
№ набору
0
0
0
0
0
0
1
1
0
0
1
0
1
1
2
0
1
0
1
0
0
3
0
1
1
1
0
1
4
1
0
0
0
1
0
5
1
0
1
0
1
0
6
1
1
0
1
0
1
7
1
1
1
1
1
1
Розглянемо реалізацію описаного алгоритму на прикладі.
Приклад 1. Виконати сумісну мінімізацію системи логічних функцій, заданої таблицею істинності (Таблиця 1). Побудувати комбінаційну схему для реалізації заданої системи функцій, використовуючи елементи І, АБО, НЕ.
Розв’язання.
1. Перший крок при реалізації даного методу мінімізації - запис кожної з функцій системи в ДДНФ, тобто у вигляді диз’юнкції мінтермів, що відповідають одиничним значенням логічних функцій. Отже, спираючись на Таблицю 1, записуємо ДДНФ трьох заданих логічних функцій:
(1) Наступний крок: формуємо множину А - з системи (1) виписуємо всі різні мінтерми, приписуючи кожному ознаку входження в функцію , , чи . Тут під ознакою маємо на увазі сукупність номерів функцій, ДДНФ яких містить даний мінтерм:
З отриманої множини мінтермів А будуємо ДДНФ допоміжної функції Z (вказуємо при цьому ознаки):
(2) 2. Далі приступаємо до знаходження простих імплікант за Квайном. Перед цим для зручності пронумеруємо кожний мін...
